package cn.edu.jxau.test;

import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.Arrays;

/**
 * @author 付大石
 */
public class Sort {

    public static void main(String[] args) throws IOException {

        int len = 10000;
        int[] arr = new int[len];
        DataInputStream in = new DataInputStream(new FileInputStream("C:\\Users\\PC-Clive\\Desktop\\data.dat"));
        for (int i = 0; i < arr.length; i++) {
            arr[i] = in.readInt();
        }
        in.close();

//        int[] arr = { 1, 4, 3, 4, 2, 4, 4 };
        System.out.println(Arrays.toString(arr));
        long start = System.nanoTime();
        sort(arr);
        long end = System.nanoTime();
        System.out.println(Arrays.toString(arr));
        System.out.println("spend tiem:" + (end - start));
    }

    /**
     * 三向切分的快速排序：适用于有大量重复输入的情况
     * 
     * 1.任意时刻，lt左边（不包括lt）的元素都小于切分元素
     * 2.任意时刻，gt右边（不包括gt）的元素都大于切分元素
     * 3.切分完成后，lt到gt的元素都等于切分元素
     * 
     * @param arr
     */
    private static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    private static void sort(int[] arr, int low, int high) {

        if (high <= low) {
            return;
        }
        int lt = low;
        int gt = high;
        int i = low + 1;
        int p = arr[low]; //切分元素
        while(i<=gt) {
            if(arr[i] < p) {
                swap(arr,lt++,i++);
            } else if(arr[i] > p) {
                swap(arr,gt--,i);
            } else {
                i++;
            }
        }
        sort(arr,low,lt-1);
        sort(arr,gt+1,high);
    }

    private static void swap(int[] arr, int i, int j) {

        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
